package Leetcode第二期;

import java.util.Arrays;

/**
 * @author : K k
 * @date : 10:30 2020/9/24
 * 给你一个整数数组 nums ，请你找出数组中乘积最大的连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。
 *
 *  
 *
 * 示例 1:
 *
 * 输入: [2,3,-2,4]
 * 输出: 6
 * 解释: 子数组 [2,3] 有最大乘积 6。
 * 示例 2:
 *
 * 输入: [-2,0,-1]
 * 输出: 0
 * 解释: 结果不能为 2, 因为 [-2,-1] 不是子数组
 */
public class 乘积最大子数组_152 {

    //思路：动态规划，公式 maxf(n)=max{fmax(n-1)*an,fmin(n-1)*an,an}
    //                   minf(n)=min{fmax(n-1)*an,fmin(n-1)*an,an}
    public int maxProduct(int[] nums) {
        int length=nums.length;
        int[] max = Arrays.copyOfRange(nums, 0, length);
        int[] min = Arrays.copyOfRange(nums, 0, length);
        for(int i=1;i<length;i++){
            max[i]=Math.max(max[i-1]*nums[i],Math.max(min[i-1]*nums[i],nums[i]));
            min[i]=Math.min(max[i-1]*nums[i],Math.min(min[i-1]*nums[i],nums[i]));
        }
        int ans=max[0];
        for(int i=1;i<length;i++){
            ans = Math.max(ans, max[i]);
        }
        return ans;
    }

    //优化，变量代替数组
    public int maxProductA(int[] nums) {
        int maxF = nums[0], minF = nums[0], ans = nums[0];
        int length = nums.length;
        for (int i = 1; i < length; ++i) {
            int mx = maxF, mn = minF;
            maxF = Math.max(mx * nums[i], Math.max(nums[i], mn * nums[i]));
            minF = Math.min(mn * nums[i], Math.min(nums[i], mx * nums[i]));
            ans = Math.max(maxF, ans);
        }
        return ans;
    }
}
